package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

/**
*作者：furong
*日期：2017年2月10日
*时间：下午6:15:16
*/
public class Q123 {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    boolean isEnd = false;

    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() <= 0) {
            return true;
        }
        if (board == null || board.length <= 0 || board[0] == null || board[0].length <= 0) {
            return false;
        }
        int n = board.length;
        int m = board[0].length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                List<Point> exclude = new ArrayList<>();
                check(board, i, j, n, m, word, 0, exclude);
                if (isEnd) {
                    return true;
                }
            }
        }
        return false;

    }

    private void check(char[][] board, int i, int j, int n, int m, String word, int k, List<Point> l) {
        if (isEnd) {
            return;
        }
        char c = board[i][j];
        if (c == word.charAt(k)) {
            if (k >= word.length() - 1) {
                isEnd = true;
                return;
            }
            if (i - 1 >= 0) {
                if (!checkPoint(i - 1, j, l)) {
                    Point p = new Point();
                    p.x = i - 1;
                    p.y = j;
                    l.add(p);
                    check(board, i - 1, j, n, m, word, k + 1, l);
                    l.remove(p);
                }
            }
            if (j - 1 >= 0) {
                if (!checkPoint(i, j - 1, l)) {
                    Point p = new Point();
                    p.x = i;
                    p.y = j - 1;
                    l.add(p);
                    check(board, i, j - 1, n, m, word, k + 1, l);
                    l.remove(p);
                }
            }
            if (i + 1 < n) {
                if (!checkPoint(i + 1, j, l)) {
                    Point p = new Point();
                    p.x = i + 1;
                    p.y = j;
                    l.add(p);
                    check(board, i + 1, j, n, m, word, k + 1, l);
                    l.remove(p);
                }
            }
            if (j + 1 < m) {
                if (!checkPoint(i, j + 1, l)) {
                    Point p = new Point();
                    p.x = i;
                    p.y = j + 1;
                    l.add(p);
                    check(board, i, j + 1, n, m, word, k + 1, l);
                    l.remove(p);
                }
            }
        }
    }

    private boolean checkPoint(int i, int j, List<Point> l) {
        for (Point p : l) {
            if (p.x == i && p.y == j) {
                return true;
            }
        }
        return false;
    }

    class Point {
        int x;
        int y;
    }

    public static void main(String[] args) {
        char board[][] = { { 'A', 'B', 'C', 'E' },

        { 'S', 'F', 'C', 'S' },

        { 'A', 'D', 'E', 'E' } };
        // char board[][] ={{'z'}};
        System.out.println(new Q123().exist(board, "ABCCED"));
    }
}
